COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\documentstyle[11pt]{article}
C00020 ENDMK
C⊗;
\documentstyle[11pt]{article}
\font\sc=cmcsc10
\oddsidemargin 36pt		% Left margin on odd-numbered pages.
\evensidemargin 0pt		% Left margin on even-numbered pages.
\marginparwidth 0pt		% Width of marginal notes.
\marginparsep 10pt		% Horizontal space between outer margin and
				%   marginal note
\topmargin 0pt			% Nominal distance from top of page to top of
				%   box containing running head.
\headheight 0pt			% Height of box containing running head.
\headsep 0pt			% Space between running head and text.

\textheight 8.7in
\textwidth 6.0in

\makeatletter

% Changes to title macros to increase spacing and print in \bf

\def\@maketitle{\newpage
 \null
 \vskip 1.3in                 % Vertical space above title.
 \begin{center}
  {\LARGE\bf \@title \par}     % Title set in \LARGE size. 
  \vskip 3.0em                % Vertical space after title.
  {\large                        % each author set in \large, in a
   \lineskip .5em           % tabular environment
   \begin{tabular}[t]{c}\@author 
   \end{tabular}\par}                   
  \vskip 1em              % Vertical space after author.
  {\large \@date}           % Date set in \large size.
\end{center}
 \par
 \vskip 1.5em}                % Vertical space after date.

\makeatother
%%% today macro from letterhead
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\newenvironment{required}%
{\begin{itemize}\renewcommand{\labelitemi}{$\bullet$}}%
{\end{itemize}}

\newcommand{\paper}{\item}
\newcommand{\notes}{\item[]}

\newenvironment{optional}%
{\begin{itemize}\renewcommand{\labelitemi}{$\circ$}}%
{\end{itemize}}

\hyphenation{Leves-que}

\title{Proposed Reading List for a Depth Area of the \\
        Qualifying Examination in Artificial Intelligence}
\author{R. Michael Young}

\date{Computer Science Department \\ Stanford University}

\begin{document}
\maketitle
\thispagestyle{empty}

\vspace*{1.3in}
\begin{abstract}

This document contains the reading list for a proposed depth
areas of the Qualifying Examination
in Artificial Intelligence.  This depth area, entitled Formal Models
of Inter-Agent Communication, covers areas in the
theory of communication, speech act theory, reasoning about knowledge
and belief, temporal and nonmonotonic reasoning and various
approaches to coordinated action focusing on the representation of
agents and the effects of communication.

\end{abstract}

\newpage
\pagenumbering{arabic}		% resets page # to 1

\section*{Overview} 
This document contains the reading list for a proposed depth
areas of the Qualifying Examination
in Artificial Intelligence.  This depth area, entitled Formal Models
of Inter-Agent Communication, covers areas in the
theory of communication, speech act theory, reasoning about knowledge
and belief, temporal and nonmonotonic reasoning and various
approaches to coordinated action focusing on the representation of
agents and the effects of communication.

This document attempts to demonstrate that the following section
defines an acceptable depth area in Artificial Intelligence research.
I do this by enumerating references which show that the field is
sufficiently developed to have a substantial core of foundational
work, sufficiently deep to warrant a focus of research which will lead
to a thesis and sufficiently broad to encompass approximately the same
scope as other previously-accepted depth areas.


\section{Formal Models of Inter-Agent Communication}

\subsection{Communication}

This section contains the papers which constitute the substance of
this depth area.

\label{sec:comm}

\begin{required}


\paper Allen, {\em Recognizing Intentions From Natural Language Utterances}. 

\paper  Allen and Perrault, {\em
Analyzing Intention in Utterances}. \\
The use of intention in analysing communiction.  Particularly the
ability to produce and understand indirect speech acts.

\paper Appelt, {\em Planning English Refering Expressions}. \\
This paper briefly describes Appelt's thesis work; generating
phrases in English from formal descriptions of the world, including a
model of the internal state of the hearer.

\paper Appelt and Konolige, {\em A Practical Nonmonotonic Theory for
Reasoning about Speech Acts}.  \\
Continues Perrault's ideas of Speech Acts cast in a a framework of
autoepistemic logic.  It demonstrates problems with Perrault's
approach and several attractive features of AE logic in this
application. 

\paper Austin, How to Do Things With Words. \\ One of the original
works on speech act theory in linguistics. 

\paper Cohen and Perrault, {\em Elements of a Plan-Based Theory of
Speech Acts}.  Defines operators for speech actions and demonstrates
the compositional adequacy of these operators, allowing the modeling
of speech acts as planning operators.

\paper Cohen and Levesque, {\em Persitence, Intention and Committment}.  \\
Discusses at length the desirable properties which a system of
autonomous, communicating agents based on a pseudo-BDI model must possess.


\paper Georgeff, {\em Communication and Interaction in Multi-Agent
Planning}. 


\paper Kautz {\em A Circumscriptive Theory of Plan Recognition}.  \\
This paper covers the use of circumscription in plan recognition, with
applications to recognizing intentions, goals, etc, in the context of
speech acts.


\paper McCarthy, {\em Elephant 2000}.   \\
A programming language for intelligent machines which is based ont eh
semantics of speech act theory.


\paper Perrault, {\em An Application of Default Logic to Speech Act
Theory}.  \\
The first work creating a nonmonotonic axiomatization of speech act
theory. 


\paper Searle, {\em Speech Acts: An Essay in the Philosophy of
Language}. \\
One of the original works on speech acts.


\paper Shoham, {\em Agent-Oriented Programming}.

\paper Werner, {\em Cooperating Agents: A Unified Theory of
communication and Social Structure}.

\paper Winograd and Flores, {\em Phenomenological Foundations of
Language, Cognition and Computation}.  \\
Discusses the critical role
communication plays in intelligent systems.  Describes the
philosophical importance of communication in problem solving and
analyzes the limitations of artificial systems in this context.



\end{required}

\subsection{Representations for Multi-Agent Action}

This section contains papers which describe work that is to be
considered as background and should not be given equal weight when
considering the scope of the depth area.  For instance, although
Reiter's survey paper on nonmonotonic logic is included here, it is
present only because a fair amount of the work described in the
previous section relies on concepts related to nonmonotonic reasoning.

\begin{required}

\paper Allen, {\em Towards a General Theory of Action and Time}.

\paper Genesereth and Nilsson, {\em Logical Foundations of Artificial Intelligence}. \\
The chapters on nonmonotonic reasoning (chapter 6), knowledge and
belief (chapter 9) and intelligent-agent architectures (chapter 13).


\paper Halpern and Moses, {\em Knowledge and Common Knowledge in a
Distributed Environment}. 

\paper Konolige,  {\em A First-Order Formalization of Knowledge and
Action for a Mulit-Agent Planning System}. 


\paper Moore,  {\em A Formal Theory of Knowledge and Action}.  

\paper Pollack, Israel and Bratman, {\em Toward an Architecture for
Resource-Bounded Agents}.



\paper Reiter, {\em Nonmonotonic Reasoning}.


\paper Shoham, {\em Reasoning About Change: Time and Causation from
the standpoint of Artificial Intelligence}. \\
Thesis incorporating a temporal and nonmonotonic logic for reasoning
by agents.

\end{required}

\newpage
\begin{thebibliography}{99}

\bibitem{Allen} Allen, J., Recognizing Intentions from Natural
Language Utterances, in {\em Computational Models of Discourse}, Brady
and Berwick, eds., MIT Press, 1983.

\bibitem{Allen} Allen, J., Towards a General Theory of Action and
Time, in {\em Artificial Intelligence}, 23(2), 1980.

\bibitem{Allen-Perrault} Allen, J., and Perrault, C. R., {\em
Analyzing Intention in Utterances}, in Readings in Natural
Langauge Processing, Grosz, et al, eds. Morgan Kaufman, 1986.

\bibitem{Kurt} Appelt, D., {\em Planning English Refering Expressions}

\bibitem{Kurt} Appelt, D. and Konolige, K., ``A Practical Nonmonotonic
Theory for Reasoning about Speech Acts," to appear in {\em
Proceedings of the 1988 Conference of the Association for
Computational Linguistics.} 

\bibitem{Kurt} Austin, {\em How to Do Things With Words}, Oxford
Press, 1963.


\bibitem{Cohen-Perrault} Cohen, P., and Perrault, C. R., {\em Elements
of a Plan-Based Theory of Speech Acts}, in Readings in Natural
Langauge Processing, Grosz, et al, eds. Morgan Kaufman, 1986.

\bibitem{CohenLevesque} Cohen, P., and Levesque, H., {\em Persitence,
Intention and Committment}, SRI technical report 415, February 1987.



\bibitem{Genesereth} Genesereth, M., and Nilsson, N., 
{\em Logical Foundations of Artificial Intelligence}, Morgan Kaufmann,
1987. 


\bibitem{Georgeff} Georgeff, M., {\em Communication and Interaction in
Multi-Agent Planning}, Proceedings of the National Conference on
Artificial Intelligence, Morgan Kaufman, 1983.

\bibitem{HalpernMoses} Halpern, J., and Moses, Y., {\em Knowledge and
Common Knowledge in a Distributed Environment}, IBM Technical Report. 

\bibitem{Kautz} Kautz, H., {\em A Circumscriptive Theory of
Plan-Recognition}.

\bibitem{Konolige} Konolige, K., {\em A First-Order Formalization of
Knowledge and Action for a Multi-Agent Planning System}, SRI Technical
Report. 

\bibitem{McCarthy} McCarthy, J., {\em Elephant 2000}, in preparation.

\bibitem{Moore} Moore, R., A Formal Theory of Knowledge and Action, in
{\em Formal Theories of the Commonsense World}, Hobbs and Moore, eds.,
Ablex, 1985.

\bibitem{Perrault} Perrault, C. R., {\em An Application of Default
Logic to Speech Act Theory,}  CSLI Technical 
Report CSLI-87-90, 1987.

\paper Pollack, M., Israel, D., and Bratman, M., {\em Toward an
Architecture for 
Resource-Bounded Agents}, CSLI Technical Report CSLI-87-104, August,
1987.

\bibitem{Reiter:nm} Reiter, R., Nonmonotonic reasoning, in {\em Annual
Review of Computer Science}, 1987. 


\bibitem{Searle} Searle, J. R., {\em Speech Acts: An essay in the
philosophy of language}, Cambridge: Cambridge University Press, 1969. 

\bibitem{Thesis} Shoham, Y., {\em Reasoning About Change: Time and
Causation from the Standpoint of Artificial Intelligence,}  Ph.D
Thesis, Yale University, 1986.

\bibitem{AOP} Shoham,Y., {\em Agent-Oriented Programming}, Stanford
University Department of Computer Science Technical Report, in preparation.

\bibitem{Werner} Cooperating Agents: A Unified Theory of
communication and Social Structure, in {\em Distributed Artificial
Intelligence}, vol II, Gasser and Huhns, eds., Morgan Kaufmann, 1989.

\bibitem{Winograd:flores} Winograd, T. and Flores, F.,
{\em Understanding Computers and Cognition}. Ablex, 1986.

\end{thebibliography}
\end{document}